

// 494 .目标和
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        // 经典的背包问题 , dp[i][j]表示选择到i位置时 , 和为j的方法数
        int n = nums.size();
        int sum = accumulate(nums.begin() , nums.end() , 0);
        if(sum < target) return 0;

        vector<vector<int>> dp(n + 1, vector<int>(2*sum + 1));      // 和可能为负数
        // 进行初始化
        dp[0][sum] = 1;

        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 0 ; j <= 2*sum ; j++)
            {
                if(j - nums[i - 1] >= 0) dp[i][j] += dp[i - 1][j - nums[i - 1]];
                if(j + nums[i - 1] <= 2*sum) dp[i][j] += dp[i - 1][j + nums[i - 1]];
            }
        }
        return dp[n][sum + target];
    }
};